#pragma once

#include <test.h>
#include <functional>

namespace Y {
    inline size_t Parent(size_t idx) {
        return idx >> 1;
    }

    inline size_t Left(size_t idx) {
        return (idx << 1) + 1;
    }

    inline size_t Right(size_t idx) {
        return (idx << 1) + 2;
    }

    template<typename TElement>
    void MaxHeapify(std::vector<TElement> &v, size_t i, size_t heapSize) {
        const size_t n = heapSize;
        const size_t l = Left(i);
        const size_t r = Right(i);
        size_t largest = i;
        if (l < n && v[l] > v[i])
            largest = l;
        if (r < n && v[r] > v[largest])
            largest = r;
        if (largest != i) {
            std::swap(v[largest], v[i]);
            MaxHeapify(v, largest, heapSize);
        }
    }

    template<typename TElement>
    size_t BuildMaxHeap(std::vector<TElement> &v) {
        const size_t heapSize = v.size();
        for (size_t i = heapSize / 2; i > 0; --i)
            MaxHeapify(v, i-1, heapSize);
    }

    template<typename TElement, typename TPredicate>
    void HeapSort(std::vector<TElement> &v, TPredicate predicate = TPredicate()) {
        const size_t n = v.size();
        size_t heapSize = v.size();
        BuildMaxHeap(v);
        for (size_t i = n-1; i >= 1; --i) {
            std::swap(v[0], v[i]);
            --heapSize;
            MaxHeapify(v, 0, heapSize);
        }
    }

    template<typename TElement>
    void HeapSort(std::vector<TElement> &v) {
        HeapSort(v, std::less<TElement>());
    }

    /*template<typename TElement>
    void HeapSort(std::vector<TElement> &v) {
        HeapSort(v, std::less<TElement>());
    }*/

    /*
    template<typename TElement, typename TIterator, typename TPredicate>
    void HeapSort(TIterator begin, TIterator end, TPredicate predicate) {
        //
    }

    template<typename TElement, typename TIterator, typename TPredicate>
    void HeapSort(TIterator begin, TIterator end) {
        HeapSort(begin, end, std::less<TElement>());
    }
    */

    class HeapSortTest : public ISortTest {
    protected:
        std::string GetName() const;
        void Sort(std::vector<int> &v);
    };
} // namespace Y
